package com.example.linked.doublepointers;

import com.example.linked.ListNode;

public class Leetcode206_ReverseList {
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        ListNode cur;
        node1.next = node2;
//        node2.next = node3;
//        node3.next = node4;
//        node4.next = node5;
        cur = node1;
        while (cur != null) {
            System.out.print(cur.val + "-->");
            cur = cur.next;
        }
        System.out.println("\n==================");
        ListNode reverseList = reverseList2(node1);
        System.out.println(reverseList);
        cur = reverseList;
        while (cur != null) {
            System.out.print(cur.val + "-->");
            cur = cur.next;
        }
    }

    /**
     * 解法一:双指针法
     * <p>
     * 核心：将cur.next指向pre
     *
     * @param head
     * @return
     */
    public static ListNode reverseList1(ListNode head) {
        ListNode cur = head, pre = null;
        // 用于暂存后继节点 cur.next，
        // 目的是为了在cur.next指向pre后，能找到下一次反转的节点
        ListNode tmp;
        while (cur != null) {
            tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    /**
     * 解法二:递归实现翻转
     * <p>
     * 反转头结点和头结点以外的节点（递归下去）
     * 递：将链表不断拆成头结点和头结点以外的节点，直到只有一个节点时为止
     * 归：完成反转动作
     *
     * @param head
     * @return
     */
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur = reverseList2(head.next);
        // 完成反转动作
        head.next.next = head;
        head.next = null;
        return cur;
    }

}
